洛谷 AT_dp_v · 难度 提高+/省选−

题目描述

有一棵包含 $N$ 个顶点的树。顶点编号为 $1,2,\dots ,N$。对于每个 $i$（$1\le i\le N-1$），第 $i$ 条边连接顶点 $x_i$ 和 $y_i$。

太郎君打算将每个顶点涂成白色或黑色。此时，需要保证任意两个黑色顶点之间，都可以仅通过黑色顶点相互到达。

给定一个正整数 $M$。对于每个 $v$（$1\le v\le N$），请回答以下问题：

• 以顶点 $v$ 为黑色的所有顶点染色方案有多少种？请输出对 $M$ 取模的结果。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$
$x_1$ $y_1$
$x_2$ $y_2$
$⋮$
$x_{N-1}$ $y_{N-1}$

输出格式

输出 $N$ 行。对于每个 $v$（$1\le v\le N$），第 $v$ 行输出以下问题的答案：

• 以顶点 $v$ 为黑色的所有顶点染色方案有多少种？请输出对 $M$ 取模的结果。

说明/提示

限制条件

• 所有输入均为整数。
• $1\le N\le {10}^5$
• $2\le M\le {10}^9$
• $1\le x_i,y_i\le N$
• 给定的图为一棵树。

样例解释 1

顶点染色的方案共有 $7$ 种。在这些方案中，顶点 $1$ 为黑色的有 $3$ 种，顶点 $2$ 为黑色的有 $4$ 种，顶点 $3$ 为黑色的有 $3$ 种。

样例解释 4

不要忘记输出答案对 $M$ 取模的结果。

由 ChatGPT 4.1 翻译

样例

样例 1

输入

3 100
1 2
2 3

输出

3
4
3

样例 2

输入

4 100
1 2
1 3
1 4

输出

8
5
5
5

样例 3

输入

1 100

输出

1

样例 4

输入

10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7

输出

0
0
1
1
1
0
1
0
1
1